package com.lwl.Algorithmic_data_structure.class19暴力递归2动态规划;


import com.lwl.Algorithmic_data_structure.动态规划.class1.Code04_LongestCommonSubsequence;

/**
 * @author lwl
 * @Description 最长公共子序列(子序列不要求连续)
 * @date 2023/6/7 19:56
 */
public class Code04LongestCommonSubsequence {

    public static void main(String[] args) {
//        String str1 = "aabbbb";
                String str1 = "1q23e45w6vasdwqsanckjxcvlkhlxckvjbjewqdajwhkj";
                String str2 = "q654e321wsafasdawkldwqhkjehdkajbsdbakjsdbasjkbdjbmcxvn";
//        String str2 = "aqabbbbb";
//        System.out.println(longestCommonSubsequence(str1, str2));
        System.out.println(longestCommonSubsequence2(str1, str2));
        System.out.println(longestCommonSubsequence3(str1, str2));
        System.out.println(Code04_LongestCommonSubsequence.longestCommonSubsequence2(str1, str2));
    }

    static private int longestCommonSubsequence3(String str1, String str2) {
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];
        for (int i = 1; i <= str1.length(); i++) {
            for (int j = 1; j <= str2.length(); j++) {
                int p1 = dp[i - 1][j];
                int p2 = dp[i][j - 1];
                int p3 = dp[i - 1][j - 1];
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    p3++;
                }
                dp[i][j] = Math.max(Math.max(p1, p2), p3);
            }
        }
        return dp[str1.length()][str2.length()];
    }

    static private int longestCommonSubsequence2(String str1, String str2) {
        int[][] dp = new int[str1.length()][str2.length()];
        dp[0][0] = str1.charAt(0) == str2.charAt(0) ? 1 : 0;
        for (int i = 1; i < str1.length(); i++) {
            dp[i][0] = str1.charAt(i) == str2.charAt(0) ? 1 : dp[i - 1][0];
        }
        for (int i = 1; i < str2.length(); i++) {
            dp[0][i] = str2.charAt(i) == str1.charAt(0) ? 1 : dp[0][i - 1];
        }
        for (int i = 1; i < str1.length(); i++) {
            for (int j = 1; j < str2.length(); j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j]);
                dp[i][j] = Math.max(dp[i][j - 1], dp[i][j]);
                if (str1.charAt(i) == str2.charAt(j)) {
                    dp[i][j] = Math.max(dp[i - 1][j - 1] + 1, dp[i][j]);
                }
            }
        }
        return dp[str1.length() - 1][str2.length() - 1];
    }

    static private int longestCommonSubsequence(String str1, String str2) {
        return process(str1.toCharArray(), str1.length() - 1, str2.toCharArray(), str2.length() - 1);
    }

    /**
     * 返回 str1 (0 .. idx1) 和 str2（0 .. idx2）的公共子序列
     */
    private static int process(char[] str1, int idx1, char[] str2, int idx2) {
        if (idx1 == -1 || idx2 == -1) {
            return 0;
        }
        int p1 = process(str1, idx1 - 1, str2, idx2);
        int p2 = process(str1, idx1, str2, idx2 - 1);
        int p3 = 0;
        if (str1[idx1] == str2[idx2]) {
            p3 = process(str1, idx1 - 1, str2, idx2 - 1) + 1;
        }
        return Math.max(Math.max(p1, p2), p3);
    }

}
